package com.copa.l101;

import java.util.LinkedList;
import java.util.Queue;

/**
 * @author copa
 * @createDate 2022-07-13 17:52
 * @function 迭代法（这是我能想到的...）
 */
public class Test1 {

    public boolean isSymmetric(TreeNode root) {
        return check(root, root);
    }

    private boolean check(TreeNode left, TreeNode right) {
        // 因为需要成对比较，所以根节点我也当两个了
        Queue<TreeNode> queue = new LinkedList<>();
        queue.add(left);
        queue.add(right);
        while (queue.size() != 0) {
            TreeNode treeNodeLeft = queue.poll();
            TreeNode treeNodeRight = queue.poll();
            if (treeNodeLeft == null && treeNodeRight == null) {
                // 如果左右子树都没有那就证明是一样的，可以继续比较余下队列的节点
                continue;
            }
            if ((treeNodeLeft == null || treeNodeRight == null) || treeNodeLeft.val != treeNodeRight.val) {
                // 如果左右子树有一边为空或者是值不相等，那么必定会不相等
                return false;
            }
            // 注意加到队列的顺序，因为是对称二叉树，所以若一个节点往左走，则另一个节点往右走，反之亦然
            // 这样做，能方便同时取队列的前两个进行比较
            queue.add(treeNodeLeft.left);
            queue.add(treeNodeRight.right);

            queue.add(treeNodeLeft.right);
            queue.add(treeNodeRight.left);
        }
        return true;
    }

    public static void main(String[] args) {
        TreeNode root = new TreeNode(1);
        root.left = new TreeNode(2);
        root.left.left = new TreeNode(3);
        root.left.right = new TreeNode(4);
        root.right = new TreeNode(2);
        root.right.left = new TreeNode(4);
        root.right.right = new TreeNode(3);
        System.out.println(new Test1().isSymmetric(root));
    }
}
